package DataStructure_ZL.二叉树.堆的实现;

import java.util.Arrays;
import java.util.PriorityQueue;

//堆的实现（优先级队列）
public class testHeap {

    public int[] elem;
    public int usedSize;

    //大根堆（大堆）的实现，小根堆只需要把小于号换一下
    public testHeap() {
        this.elem = new int[10];
    }

    /**
     * 建堆的时间复杂度：
     *
     * @param array
     */
    public void createHeap(int[] array) {
        //这一步不算是必须的。这里只是准备数据
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }

        for (int p = (usedSize - 1 - 1) / 2; p >= 0; p--) {
            shiftDown(p, usedSize);
        }
    }

    /**
     * @param root 是每棵子树的根节点的下标
     * @param len  是每棵子树调整结束的结束条件
     *             向下调整的时间复杂度：O(logn)
     */
    private void shiftDown(int root, int len) {
        int parent = root;
        int child = 2 * parent + 1;
        //进入这个循环，说明一定至少有一个孩子
        while (child < len) {
            //如果有孩子，找到左右孩子的最大值
            if (child + 1 < len && elem[child] < elem[child + 1]) {
                child++;
            }
            //child下标一定保存的是左右孩子最大值的下标
            //接下来，孩子的最大值和根节点去比较大小
            if (elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;//开始更新下标，继续看下面的子树是不是大根堆
                child = 2 * parent + 1;
            } else {
                break;//此时说明已经是大根堆，不需要进行再次调整了
            }
        }
    }


    //在大根堆插入一个数，保证插入后还是大根堆
    public void push(int val) {
        //判断是否为满
        if (elem.length == usedSize) elem = Arrays.copyOf(elem, 2 * elem.length);
        elem[usedSize] = val;

        int parent=(usedSize-1)/2;
        int child=usedSize;

        while(child>0){
            if (elem[child]>elem[parent]){
                int temp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=temp;
                child=parent;
                parent=(parent-1)/2;
            }else{
                break;
            }
        }
        usedSize++;
    }

    //删除顶部元素（优先级最高的元素）
    public void pollHeap() {
        if(usedSize==0) {
            System.out.println("优先级队列为空！");
            return;
        }
        int tmp = elem[0];
        elem[0] = elem[usedSize-1];
        elem[usedSize-1] = tmp;
        usedSize--;
        shiftDown(0,usedSize);
    }
    //查找指定元素的索引位置
    private int findVal(int val) {
        for (int i=0;i<usedSize;i++){
            if (elem[i]==val)return i;
        }
        return -1;//不存在该值返回-1；
    }

    //获取堆顶元素
    public int peekVal(){
        //判断是否为空
        if (usedSize==0) throw new RuntimeException("队列为空");
        return elem[0];
    }

    /*
    设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
     */
    public int[] smallestK(int[] arr, int k) {
        if (arr.length == 0 || k <= 0) return new int[0];
        PriorityQueue<Integer> iu = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int i = 0; i < arr.length; i++) {
            if (iu.size() < k) {
                iu.offer(arr[i]);
            } else {
                if (arr[i] < iu.peek()) {
                    iu.poll();
                    iu.offer(arr[i]);
                }
            }

        }
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = iu.poll();
        }
        return result;
    }
    //堆排序即利用堆的思想来进行排序(这里是升序1~+，因为用的是自
    // 定义的优先队列是大根堆，（升序用大根堆，降序用小根堆）)
    public void heapSort(){
        int end=usedSize-1;
        while(end>0){
            int temp=elem[0];
            elem[0]=elem[end];
            elem[end]=temp;
            shiftDown(0,end);
            end--;
        }
    }


}











